//
// Created by yangchao on 2022/5/10.
// 69. x 的平方根 : https://leetcode.cn/problems/sqrtx/
//

class MySqrt{
public:
    /*二分查找*/
    int mySqrt(int x) {
       if (x <= 1) return x;
       int left = 1, right = x / 2;
       //在区间[left,right]查找目标元素
        while (left <= right) {
            int mid = (left + right) / 2;
            if (mid > x / mid) {
                right = mid - 1;
            } else if (mid < x / mid) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return left-1;
    }
};

